# -*-coding = utf-8-*-
import requests


def get_mix_num(n):
    # 1=<n<=200
    try:
        y_max = int(n / 9)
        for y in range(y_max, 0, -1):
            x_max = n - 9 * y
            if x_max % 4 == 0:
                print n, y, x_max / 4, y + x_max / 4
    except Exception as err:
        print err


class Solution(object):
    def coinChange(self, coins_list, amount):
        if len(coins_list) <= 0:
            return -1
        if len(coins_list) == 1:
            tmp_num = amount % coins_list[0]
            if tmp_num == 0:
                return amount / coins_list[0]
            return -1

        num = 0
        # coins = [1, 2, 5]
        # coins = [5,2,1]
        for coin in coins_list[::-1]:
            print "amount:{}, coin:{}, num:{}".format(amount, coin, num)
            if amount % coin == 0:
                print "*" * 50
                print amount, coin, num
                tmp_num = amount / coin
                num += tmp_num
                amount = amount - coin * tmp_num
                print amount, coin, num
                print "=" * 50
            else:
                print "*" * 50
                print amount, coin, num
                tmp_num = int(amount / coin)
                num += tmp_num
                amount = amount - coin * tmp_num
                print amount, coin, num
                print "=" * 50
            if amount == 0:
                print "num = %d\n" % num
                return num
        return -1


if __name__ == '__main__':
    # for i in range(200):
    #     get_mix_num(n=i)
    # coins = [1, 2, 5]
    # coins = [2]
    coins = [1]
    amount = 2
    # print get_coin_mix_num(amount, coins)

    pass
